package leetcode.code0778;

import java.util.PriorityQueue;

public class Solution1 extends Solution778 {

	private int N;

	@Override
	public int swimInWater(int[][] grid) {
		N = grid.length;
		PriorityQueue<int[]> water = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
		water.add(new int[] { 0, 0, grid[0][0] });
		int ans = 0;
		boolean[][] checked = new boolean[N][N];
		checked[0][0] = true;
		while (!water.isEmpty()) {
			int[] pos = water.poll();
			int x = pos[0];
			int y = pos[1];
			int higth = grid[x][y];
			if (higth > ans) {
				ans = higth;
			}
			if (x == N - 1 && y == N - 1) {
				break;
			}
			this.swimTo(water, checked, x + 1, y, grid);
			this.swimTo(water, checked, x - 1, y, grid);
			this.swimTo(water, checked, x, y + 1, grid);
			this.swimTo(water, checked, x, y - 1, grid);
		}
		return ans;
	}

	private void swimTo(PriorityQueue<int[]> water, boolean[][] checked, int x, int y, int[][] grid) {
		if (x >= 0 && x < N && y >= 0 && y < N && !checked[x][y]) {
			checked[x][y] = true;
			water.add(new int[] { x, y, grid[x][y] });
		}
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
	}

}
